#include "dijkstra.h"

void Dijkstra(IGraph *graph, int startVertex, int d[], int p[])
{
	//initialize d, p
	for(int i = 0; i < graph->GetVertexCount(); i++)
	{
		d[i] = INF_DISTANCE;
		p[i] = -1;
		if(i == startVertex)
		{
			p[i] = i;
			d[i] = 0;
		}
	}

	for(int i = 1; i < graph->GetVertexCount(); i++)
	{
		//find min{d[i]}
		int nextVertex = -1;
		int pathLength = INF_DISTANCE;
		int prevVertex = -1;
		for(int j = 0; j < graph->GetVertexCount(); j++)
		{
			if(p[j] == -1)
			{
				for(int si = 0; si < graph->GetVertexCount(); si++)
				{
					if(p[si] != -1 && d[j] > d[si] + graph->GetDistance(si, j))
					{
						d[j] = d[si] + graph->GetDistance(si, j);
						prevVertex = si;
					}
				}
				if(d[j] < pathLength)
				{
					pathLength = d[j];
					nextVertex = j;
				}
			}
		}
		if(nextVertex == -1) return;
		p[nextVertex] = prevVertex;

	}
}
